Crate num_modular

This crate provides efficient Modular arithmetic operations for various integer types, including primitive integers and num-bigint. The latter option is enabled optionally.

To achieve fast modular arithmetics, convert integers to any ModularInteger implementation use static new() or associated ModularInteger::convert() functions. Some builtin implementations of ModularInteger includes MontgomeryInt and FixedMersenneInt.

Example code:

use num_modular::{ModularCoreOps, ModularInteger, MontgomeryInt};

// directly using methods in ModularCoreOps
let (x, y, m) = (12u8, 13u8, 5u8);
assert_eq!(x.mulm(y, &m), x * y % m);

// convert integers into ModularInteger
let mx = MontgomeryInt::new(x, &m);
let my = mx.convert(y); // faster than static MontgomeryInt::new(y, m)
assert_eq!((mx * my).residue(), x * y % m);

Comparison of fast division / modular arithmetics

Several fast division / modulo tricks are provided in these crate, the difference of them are listed below:

• PreModInv: pre-compute modular inverse of the divisor, only applicable to exact division
• Barret (to be implemented): pre-compute (rational approximation of) the reciprocal of the divisor, applicable to fast division and modulo
• Montgomery: Convert the dividend into a special form by shifting and pre-compute a modular inverse, only applicable to fast modulo, but faster than Barret reduction
• FixedMersenne: Specialization of modulo in form 2^P-K under 2^127.

Structs

• FixedMersenne
  A modular reducer for (pseudo) Mersenne numbers 2^P - K as modulus. It supports P up to 127 and K < 2^(P-1)
• Montgomery
  A modular reducer based on Montgomery form, only supports odd modulus.
• Normalized2by1Divisor
  Divide a DoubleWord by a prearranged divisor.
• Normalized3by2Divisor
  Divide a 3-Word by a prearranged DoubleWord divisor.
• PreModInv
  Pre-computing the modular inverse for fast divisibility check.
• PreMulInv1by1
  Divide a Word by a prearranged divisor.
• PreMulInv2by1
  A wrapper of Normalized2by1Divisor that can be used as a Reducer
• PreMulInv3by2
  A wrapper of Normalized3by2Divisor that can be used as a Reducer
• ReducedInt
  An integer in a modulo ring
• Vanilla
  A plain reducer that just use normal Rem operators. It will keep the integer in range [0, modulus) after each operation.
• udouble
  A double width integer type based on the largest built-in integer type umax (currently u128), and to support double-width operations on it is the only goal for this type.

Traits

• DivExact
  Utility function for exact division, with precomputed helper values
• ModularAbs
  Provides a utility function to convert signed integers into unsigned modular form
• ModularCoreOps
  Core modular arithmetic operations.
• ModularInteger
  Represents an number defined in a modulo ring ℤ/nℤ
• ModularOps
  Collection of common modular arithmetic operations
• ModularPow
  Modular power functions
• ModularRefOps
  Collection of operations similar to ModularOps, but takes operands with references
• ModularSymbols
  Math symbols related to modular arithmetics
• ModularUnaryOps
  Core unary modular arithmetics
• Reducer
  A modular reducer that can ensure that the operations on integers are all performed in a modular ring.

Type Aliases

• FixedMersenneInt
  An integer in modulo ring with a fixed (pseudo) Mersenne number as modulus
• MontgomeryInt
  An integer in modulo ring based on Montgomery form
• VanillaInt
  An integer in modulo ring based on conventional Rem operations
• umax
  Alias of the builtin integer type with max width (currently u128)